//给定两个整数数组，preorder 和 postorder ，其中 preorder 是一个具有 无重复 值的二叉树的前序遍历，postorder 是同一棵
//树的后序遍历，重构并返回二叉树。 
//
// 如果存在多个答案，您可以返回其中 任何 一个。 
//
// 
//
// 示例 1： 
//
// 
//
// 
//输入：preorder = [1,2,4,5,3,6,7], postorder = [4,5,2,6,7,3,1]
//输出：[1,2,3,4,5,6,7]
// 
//
// 示例 2: 
//
// 
//输入: preorder = [1], postorder = [1]
//输出: [1]
// 
//
// 
//
// 提示： 
//
// 
// 1 <= preorder.length <= 30 
// 1 <= preorder[i] <= preorder.length 
// preorder 中所有值都 不同 
// postorder.length == preorder.length 
// 1 <= postorder[i] <= postorder.length 
// postorder 中所有值都 不同 
// 保证 preorder 和 postorder 是同一棵二叉树的前序遍历和后序遍历 
// 
//
// Related Topics 树 数组 哈希表 分治 二叉树 👍 373 👎 0

package leetcode.editor.cn;

import java.util.HashMap;
import java.util.Map;

//java:根据前序和后序遍历构造二叉树
public class Q0889ConstructBinaryTreeFromPreorderAndPostorderTraversal {
    public static void main(String[] args){
        Solution solution = new Q0889ConstructBinaryTreeFromPreorderAndPostorderTraversal().new Solution();
        solution.constructFromPrePost(new int[]{1,2,4,5,3,6,7}, new int[]{4,5,2,6,7,3,1});
    }
    //leetcode submit region begin(Prohibit modification and deletion)
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {

    Map<Integer, Integer> posMap;
    int[] preorder;
    int[] postorder;

    public TreeNode constructFromPrePost(int[] preorder, int[] postorder) {
        this.preorder = preorder;
        this.postorder = postorder;
        posMap = new HashMap<>();
        for (int i = 0; i < postorder.length; i++) {
            posMap.put(postorder[i], i);
        }
        return constructTree( 0, preorder.length - 1, 0, postorder.length - 1);
    }

    /**
     *
     * @param pl 前序数组左指针
     * @param pr 前序数组右指针
     * @param ppl 后序数组左指针
     * @param ppr 后序数组右指针
     * @return
     */
    private TreeNode constructTree(int pl, int pr, int ppl, int ppr) {
        if (pl > pr || ppl > ppr) {
            return null;
        }
        TreeNode root = new TreeNode(preorder[pl]);
        if (pl == pr || ppl == ppr) {
            return root;
        }
        // 前序遍历序列中下一个是左节点
        int pos = posMap.get(preorder[pl + 1]);
        // 后序遍历中 [ppl, pos]是左子树部分，pos就是前序遍历某个值在后续遍历中的位置
        // pl + 1 是左节点; pos - ppl + 1 是后序遍历中左子树的个数；[pl, pl + pos - ppl + 1] 是前序遍历中左子树的部分；[ppl, pos]后序遍历中左子树的部分
        root.left = this.constructTree(pl + 1, pl + pos - ppl + 1, ppl, pos);
        // 后序遍历中 [pos + 1， ppr - 1]是右子树部分，pos就是前序遍历某个值在后续遍历中的位置
        // [pl + pos - ppl + 2,pr] 是前序遍历中右子树的部分；[pos + 1, ppr - 1]后序遍历中右子树的部分， ppr - 1 是因为 ppr是根节点，即pl
        root.right = this.constructTree( pl + pos - ppl + 2, pr, pos + 1, ppr - 1);
        return root;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}